import operator
from math import log

from matplotlib import pyplot as plt

from 机器学习.决策树.draw_tree import createplot

'''
分类值:
unacc, acc, good, vgood
属性值:
buying,maint,doors,persons,lug_boot,safety
'''


# 计算熵不纯度
def Entropy_Impurity(dataset):
    num_dataset = len(dataset)  # 数据集实体数量
    labelCounts = {}  # 用来储存的字典
    for data in dataset:  # 先将所有可分类的特征储存在字典中
        currentLabel = data[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0  # 该特征初始数量为0
        labelCounts[currentLabel] += 1  # 已存在就数量+1
        impurity = 0.0  # 样本的熵不纯度
        for key in labelCounts:  # 遍历每个分类
            prob = float(labelCounts[key]) / num_dataset  # p
            impurity -= prob * log(prob, 2)  # 熵不纯度定义
    return impurity


# 熵越高，则说明混合的数据也越多

# 导入的数据集是txt格式，将其数据提取出来并转换为矩阵模式
def fileMatrix(filename):
    fr = open(filename)
    lists = fr.readlines()
    listNum = []
    for k in lists:
        listNum.append(k.strip().split(','))
    return listNum


# 按照特征划分数据集，比如按照安全性，将安全性划分出来，将其他数据再划分出来
def splitDataSet(dataset, axis, value):  # value 是特征，将其分割出来
    # 1.创建新的list对象
    retDataSet = []
    for featVec in dataset:
        if featVec[axis] == value:  # 将特征和结果分离出来
            # 2.抽取
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)  # 数据连接，保证每个数据的完整性
    return retDataSet


'''#test:
a = ['1','2','3']
b = ['4','5','6']
a.append(b)
print(a)
['1', '2', '3', ['4', '5', '6']]
'''


# 开始选取叶子节点(即可用于分类的特征)
def judgeLeaf(dataset):
    numEigenvalue = len(dataset[0]) - 1  # 计算特征的数量，即数据集第一行的个数-1
    datasetEntropy = Entropy_Impurity(dataset)  # 先计算每个特征的信息熵
    bestInfoGain = 0.0  # 选取最好的信息增益点
    bestFeature = -1  # 最好的划分特征
    for i in range(numEigenvalue):  # 开始遍历每个特征
        featList = [example[i] for example in dataset]
        uniqueValues = set(featList)  # 在这个特征下所有可能的取值,同时去除重复值
        newEntropy = 0.0
        for value in uniqueValues:
            subDataset = splitDataSet(dataset, i, value)  # 抽取在该特征的每个取值下其他特征的值组成新的子数据集
            prob = len(subDataset) / float(len(dataset))  # 计算该特征下的每一个取值对应的概率（或者说所占的比重）
            newEntropy += prob * Entropy_Impurity(subDataset)  # 计算该特征下每一个取值的子数据集的信息熵
        InfoGain = datasetEntropy - newEntropy  # 计算每个特征的信息增益
        #  print("第%d个特征是的取值是%s，对应的信息增益值是%f"%((i+1),uniqueValues,InfoGain))
        if InfoGain > bestInfoGain:  # 信息增益越小越好
            bestInfoGain = InfoGain
            bestFeature = i
            # print("第%d个特征的信息增益最大，所以选择它作为划分的依据，其特征的取值为%s,对应的信息增益值是%f"%((i+1),uniqueValues,InfoGain)
    return bestFeature  # 返回最优节点


#    决策树构建结束的标准是该分支下面所有的数据都具有相同的分类，如果所有数据都具有相同的分类，
#    则得到的叶子结点或者终止块，任何到达这个叶子结点的必属于这个分类
def MajorItyCnt(classList):
    classCount = {}  # 创建字典
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0  # 如果现阶段的字典中缺少这一类的特征，创建到字典中并令其值为0
            classCount[vote] += 1  # 循环一次，在对应的字典索引vote的数量上加一
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        # operator.itemgetter(1)是抓取其中第2个数据的值(第一个数据是string)
        # 利用sorted方法对class count进行排序
        return sortedClassCount[0][0]


'''
   items用法:
   d = { 'Adam': 95, 'Lisa': 85, 'Bart': 59 }
   print d.items()
   [('Lisa', 85), ('Adam', 95), ('Bart', 59)]'''


def GenerateTree(dataset, labels):  # 生成决策树
    classList = [example[-1] for example in dataset]  # 提取dataset中的最后一个，即结果
    if classList.count(classList[0]) == len(classList):  # 计算classList[0]出现的次数,如果相等，说明都是属于一类，不用继续往下划分
        return classList[0]
    if len(dataset[0]) == 1:  # 看还剩下多少个属性，如果只有一个属性，但是类别标签又多个，就直接用MajorItyCnt方法进行整理  选取类别最多的作为返回值
        return MajorItyCnt(classList)
    bestFeat = judgeLeaf(dataset)  # 选取信息增益最大的特征作为下一次分类的依据
    bestFeatLabel = labels[bestFeat]  # 选取特征对应的标签
    myTree = {bestFeatLabel: {}}  # 创建tree字典，紧跟现阶段最优特征，下一个特征位于第二个大括号内，循环递归
    del (labels[bestFeat])  # 使用过的特征从中删除
    featValues = [example[bestFeat] for example in dataset]  # 特征值对应的该栏数据
    uniqueValues = set(featValues)  # 找到featValues所包含的所有元素，同名元素算一个
    for value in uniqueValues:
        subLabels = labels[:]  # 子标签的意思是循环一次之后会从中删除用过的标签 ，剩下的就是子标签了
        myTree[bestFeatLabel][value] = GenerateTree(splitDataSet(dataset, bestFeat, value), subLabels)  # 循环递归生成树
    return myTree


def testTree(inputTree, featLabels, testVec):
    classLabel = ''
    firstStr = list(inputTree.keys())[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = testTree(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel


def testefficiency(inputtree, labels, testdata):
    flag = 0
    for i in range(len(testdata)):
        result = testTree(inputtree, labels, testdata[i][:6])
        if result == testdata[i][-1]:
            flag += 1
        print('预测的结果是:', result, '正确的结果是:', testdata[i][-1])
    print('测试数据总量:', len(testdata), '正确数:', flag, '正确率: {:.2%}'.format(flag/len(testdata)))


dataSet = fileMatrix("D:\\PythonWork\\机器学习\\CarData.txt")
testData = fileMatrix("D:\\PythonWork\\机器学习\\CarTest.txt")

labelsOne = ['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety']  # 分类依据(特征)
myTree = GenerateTree(dataSet, labelsOne)  # 生成我的决策树
createplot(myTree)
labels = ['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety']
testefficiency(myTree, labels, testData)
